package h0817;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class ShortestPathBinaryMatrix {
    public static void main(String[] args) {
        ShortestPathBinaryMatrix solver = new ShortestPathBinaryMatrix();
        int[][] grid = {
                {0, 1},
                {1, 0}
        };
        System.out.println(solver.shortestPathBinaryMatrix(grid)); // Output: 2

    }

    private int shortestPathBinaryMatrix(int[][] matrix) {

        int m = matrix.length;
        //定义一个队列
        LinkedList<int[]> queue = new LinkedList<>();
        //TODO 第一个数字必须为0
        if (matrix[0][0]!=0){
            return -1;
        }
        queue.addLast(new int[]{0, 0, 1}); //从0，0开始
        //方向 ,八个
        int[][] direction = new int[][]{
                {-1, 0}, {1, 0}, {0, -1}, {0, 1},
                {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
        };
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] temp = queue.removeFirst();
                if (temp[0] == m - 1 && temp[1] == m - 1) return temp[2];
                for (int j = 0; j < direction.length; j++) {
                    int newI = temp[0] + direction[j][0];
                    int newJ = temp[1] + direction[j][1];
                    if (newI >= 0 && newI < m && newJ >= 0 && newJ < m && matrix[newI][newJ] != 1) {
                        matrix[newI][newJ] = 1;
                        queue.addLast(new int[]{newI, newJ,temp[2]+1});
                    }
                }
            }
        }
        return -1;
    }
}
